BZOJ 4008: [HNOI2015]亚瑟王

Description

小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。

他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂
亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。作为一个非
洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值。但他已
经多年没写过代码,连 Spaly都敲不对了,因此,希望你能帮帮小 K,让他感受一
下当欧洲人是怎样的体验。
本题中我们将考虑游戏的一个简化版模型。
玩家有一套卡牌,共 n张。游戏时,玩家将 n 张卡牌排列成某种顺序,排列后
将卡牌按从前往后依次编号为 1 ~ n。本题中,顺序已经确定,即为输入的顺序。
每张卡牌都有一个技能。第 i 张卡牌的技能发动概率为 pi,如果成功发动,则会对
敌方造成di点伤害。也只有通过发动技能,卡牌才能对敌方造成伤害。基于现实因
素以及小K非洲血统的考虑,pi不会为 0,也不会为 1,即 0 < pi < 1。
一局游戏一共有 r 轮。在每一轮中,系统将从第一张卡牌开始,按照顺序依次
考虑每张卡牌。在一轮中,对于依次考虑的每一张卡牌:
1如果这张卡牌在这一局游戏中已经发动过技能,则
1.1 如果这张卡牌不是最后一张,则跳过之(考虑下一张卡牌);
否则(是最后一张),结束这一轮游戏。
2否则(这张卡牌在这一局游戏中没有发动过技能),设这张卡牌为第 i 张
2.1将其以 pi的概率发动技能。
2.2如果技能发动,则对敌方造成 di点伤害,并结束这一轮。
2.3如果这张卡牌已经是最后一张(即 i 等于n),则结束这一轮;否则,
考虑下一张卡牌。
请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值。

Tyvj 1864 [Poetize I]守卫者的挑战

Description

打开了黑魔法师Vani的大门,队员们在迷宫般的路上漫无目的地搜寻着关押applepi的监狱的所在地。突然,眼前一道亮光闪过。“我,Nizem,是黑魔法圣殿的守卫者。如果你能通过我的挑战,那么你可以带走黑魔法圣殿的地图……”瞬间,队员们被传送到了一个擂台上,最初身边有一个容量为K的包包。
  擂台赛一共有N项挑战,各项挑战依次进行。第i项挑战有一个属性ai,如果ai>=0,表示这次挑战成功后可以再获得一个容量为ai的包包;如果ai=-1,则表示这次挑战成功后可以得到一个大小为1 的地图残片。地图残片必须装在包包里才能带出擂台,包包没有必要全部装满,但是队员们必须把 【获得的所有的】地图残片都带走(没有得到的不用考虑,只需要完成所有N项挑战后背包容量足够容纳地图残片即可),才能拼出完整的地图。并且他们至少要挑战成功L次才能离开擂台。
  队员们一筹莫展之时,善良的守卫者Nizem帮忙预估出了每项挑战成功的概率,其中第i项挑战成功的概率为pi%。现在,请你帮忙预测一下,队员们能够带上他们获得的地图残片离开擂台的概率。